Die deskriptive Komplexitätstheorie (beschreibende Komplexitätstheorie) ist ein Teilbereich der endlichen Modelltheorie, die den Zusammenhang der Ausdrucksstärke von Logiken und Komplexitätstheorie untersucht. Während Komplexitätsklassen wie NP oder PSPACE üblicherweise durch ein spezielles Maschinenmodell (üblicherweise Turingmaschinen) d...